package com.itcam.shellsort;

import java.util.Arrays;

public class ShellSort {

    public static void main(String[] args) {
        int[] a = {9, 5, 7, 12, 1, 3};
        System.out.println(Arrays.toString(a));
        shellSort(a);
        System.out.println(Arrays.toString(a));
    }

    /**
     * 希尔排序算法实现
     * @param a 待排序的整数数组
     */
    private static void shellSort(int[] a) {
        // 外层循环：控制增量 gap，初始为数组长度的一半，每次减半，直到 gap 为 1
        for (int gap = a.length / 2; gap >= 1; gap /= 2) {
            // 中层循环：遍历每个分组，从 gap 位置开始
            for (int low = gap; low < a.length; low++) {
                // 保存当前待插入的元素
                int temp = a[low];
                // 记录插入位置，初始为当前元素的前一个分组位置
                int i = low - gap;
                // 自右向左找插入位置，如果比待插入元素大，则不断右移，空出插入位置
                while (i >= 0 && temp < a[i]) {
                    a[i] = a[i + gap];
                    i -= gap;
                }
                // 找到插入位置
                if (i != low - gap) {
                    a[i + gap] = temp;
                }
            }
        }
    }
}